package com.yuw.quicksort;

import java.util.Scanner;

public class QuickSortTestdriver {

	public static void main(String[] args) {
		quicksort();
	}

	/**
	 * 快速排序算法测试
	 */
	public static void quicksort() {
		// 初始化数组
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入需要排序的数组的元素个数：");
		// 数组个数
		int count = sc.nextInt();
		// 创建数组
		int[] arr = new int[count];
		// 初始化数组
		for (int i = 0; i < count; i++) {
			System.out.println("请输入数组的第" + (i + 1) + "个元素的值：");
			int input = sc.nextInt();
			arr[i] = input;
		}
		// 快速排序算法处理
		doQuicksort(arr, 0, count - 1);
		// 显示打印结果
		printArr(arr);
	}

	/**
	 * 快速排序算法处理
	 * 
	 * @param arr   被排序的数组
	 * @param left  从左往右查找的下标
	 * @param right 从右往左查找的下标
	 */
	private static void doQuicksort(int[] arr, int left, int right) {

		// 每轮的递归结束条件：left<right (剔除一开始left=right的情况,防止陷入死循环)
		if (left < right) {
			// 设置两个临时变量（进行移动的左右下标）
			// 临时的右下标（用于从右向左移动）
			int rp = right; // right的值不能改变
			// 临时的左下标（用于从右向左移动）
			int lp = left; // right的值不能改变
			// 取收元素作为基准值
			int val = arr[lp];
			// 第一轮的处理
			// 一轮结束条件是 lp >= rp
			while (lp < rp) {
				// 从右往左查找第一个比基准值小的数
				while (rp > lp && arr[rp] >= val) {
					// 更改下标
					rp--;
				}

				// 找的值和基准值交换位置
				int temp = arr[rp];
				arr[rp] = arr[lp];
				arr[lp] = temp;

				// 从左往右查找第一个比基准值大的数
				while (rp > lp && arr[lp] <= val) {
					// 更改下标
					lp++;
				}

				// 找到的值和当前基准所在的位置进行交换
				temp = arr[lp];
				arr[lp] = arr[rp];
				arr[rp] = temp;

			}

			// while结束之后，说明这一轮中的交换处理完成
			// 把基准值放到rp和lp相遇的位置
			//arr[lp] = val;// 因为基准值一直在参与交换，所有最后rp和lp相遇的位置一定是基准值所在的位置

			// 结束时的位置就是分界点的位置
			// 递归处理左右两部分
			// 递归处理左边部分
			doQuicksort(arr, left, lp - 1);
			// 递归处理右边部分
			doQuicksort(arr, lp + 1, right);

		}
	}

	/**
	 * 打印数组元素内容
	 * 
	 * @param arr 被打印数组
	 */
	private static void printArr(int[] arr) {
		for (int i : arr) {
			System.out.print("  " + i);
		}
		// 换行
		System.out.println();
	}
}
